package com.xcc.dataStructures.demo06_algorithm;

import java.util.Arrays;

/**
 * 堆排序
 */
public class HeapSort {

    public static void main(String[] args) {
//        int[] arr = {5, 3, 2, 7, 6, 12, 1, 4, 2, 8, 10};
        int data = 8000000;//800w数据
        int[] arr = new int[data];
        for (int i = 0; i < data; i++) {
            arr[i] = (int) (Math.random() * data);
        }
        long startTime = System.currentTimeMillis();

        heapSort(arr);

        long endTime = System.currentTimeMillis();
        System.out.println("时长：" + ((endTime - startTime))); //大概耗时1581ms
    }

/**
 * 堆排序
 */
public static void heapSort(int[] arr) {
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
        adjustHeap(arr, i, arr.length);
    }

    for (int j = arr.length - 1; j > 0; j--) {
        //堆顶与最后一个元素进行交换
        int end = arr[j];
        arr[j] = arr[0];
        arr[0] = end;

        adjustHeap(arr, 0, j);
    }


}

/**
 * 构建大顶堆
 *      功能： 完成 将 以 i 对应的非叶子结点的树调整成大顶堆
 *      int arr[] = {4, 6, 8, 5, 9}; => i = 1 => adjustHeap => 得到 {4, 9, 8, 5, 6}
 * @param arr    数组
 * @param i      非叶子结点的最后一个结点
 * @param length 需要构建的长度
 */
private static void adjustHeap(int[] arr, int i, int length) {
    int temp = arr[i];

    //k指针，指向左子节点
    for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
        //如果当前右子节点的值在检索范围内，并且右子节点的值大于左子节点   将k指向右子节点
        if (k + 1 < length && arr[k] < arr[k + 1]) {
            k++;
        }
        //当前指针值大于非叶子结点值
        if (arr[k] > temp) {
            //将当前的非叶子结点赋值为其子节点中的最大值
            arr[i] = arr[k];
            //使用i记录当前交换的k的索引
            i = k;
        } else {
            break;
        }
    }

    //当 for 循环结束后，我们已经将以 i 为父结点的树的最大值，放在了 最顶(局部)
    //此时将temp赋值给调整后的位置上
    arr[i] = temp;

}

}
